# -*- coding: utf-8 -*-
'''
@Time    : 2022/8/16 15:50
@Author  : HandsomeWu
@File    : S_tree.py
@Describe:
    给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
    本质：层序遍历
* input:
    一行数组 -- 表示完全二叉树

* output
    遍历的结果
'''

# 我对 oj 平台怎么处理树不是太懂 就默认有这个结构吧
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pRoot TreeNode类
# @return int整型二维数组
#
class Solution:
    def Print(self, pRoot: TreeNode) -> List[List[int]]:
        # write code here
        # 思路: 使用双栈来实现 -- 层序遍历
        # 或者就是层序遍历 将偶数层取反 -- 队列
        if not pRoot:
            return []
        que = [pRoot]
        tre = []  # 最终的输出
        level_odd = False
        while que:
            len_s = len(que)
            level_temp = []
            for _ in range(len_s):
                node = que.pop(0)
                level_temp.append(node.val)

                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)

            # 和层序遍历不同的地方 -  这里加上奇偶层的判断
            if level_odd:
                tre.append(level_temp[::-1])
                level_odd = False
            else:
                tre.append(level_temp)
                level_odd = True

        return tre

# 思路2: 用一个list -- 奇数的时候模拟队列出队  偶数的时候模拟栈出栈
# 一个不行会混 还是俩吧  -- stak1出栈时 将下行入栈stak2 ,stak2出栈时 下行入栈stak1


